(1) Field of the Invention
The present invention relates to the field of interrogating a vector to determine vacant entries of a buffer resource of a processor. More specifically, the present invention relates to the field of performing such interrogation utilizing an internal two cycle pipeline for increased performance.
(2) Prior Art
Modern microprocessors have the ability to execute portions of several instructions in parallel during a single clock cycle. These microprocessors are called superscalar microprocessors and have pipelined and/or superscalar architecture. In effect, different stages of execution can be performed by a microprocessor during a single clock cycle for several different microprocessor instructions. For this reason and others, microprocessors having this ability must be able to keep track of and store information regarding several instructions at the same time and communicate this information to and from several different portions of the microprocessor in a parallel fashion. Also, because of the high operating frequencies of modern pipelined microprocessors, this instruction information must be transmitted very quickly, usually during a single clock cycle of an oscillator operating at 150-200 Megahertz. Therefore, it becomes advantageous to be able to communicate instructions and instruction data very quickly.
One component within a microprocessor that must receive information regarding instructions that are being executed by a microprocessor is the instruction scheduler. The instruction scheduler holds information regarding the current instructions that are pending execution as well as any data or information that is used by or in conjunction with the current instructions. The instruction scheduler has a finite memory storage capacity. Therefore, new and recent instruction information that is to be placed into the scheduler by the microprocessor must first obtain enough memory location vacancies within the instruction scheduler. That is to say, there must first be room within the scheduler before instruction information can be placed into the instruction scheduler. The scheduler contains a memory array, and associated circuitry, for holding this instruction information; this circuit is called a reservation station.
A specialized deallocation vector is used by the instruction scheduler in order to indicate to the microprocessor which entries in the reservation station are free and which are taken. In prior art implementations, the microprocessor would scan, one by one, each entry in the deallocation vector to locate one particular free entry of the instruction scheduler in order to store recent instruction data. However, with the introduction of microprocessors having superscalar architecture, the microprocessor must be able to search, at the same instant, the deallocation vector for up to several free entries to store information regarding several instructions during the same clock cycle. Further, as the time period between clock cycles shortens as microprocessors become faster and faster, it is important that the deallocation vector be interrogated very quickly as to not delay the processing of the microprocessor. Also, prior art allocation systems that vacate entries in order are not practical for microprocessors that execute instruction out of program order. What is needed is an allocation scheme that operates for out of order execution.
Also, since microprocessors are can also be pipelined, the interrogation circuitry for determining the free vacancies for a current clock cycle must take into account the effects of allocations performed in previous pipestages that may not yet have become realized within the reservation station or its deallocation vector during the current cycle. The present invention provides circuitry for handling the above latency.
Prior art implementations that are used to search a deallocation vector in order to find vacancies within the instruction scheduler do not operate fast enough to complete processing within only one clock cycle (which may be on the order of 1/150.sup.th of a microsecond) or within one half clock cycle (which may be 1/300.sup.th of a microsecond) of modern superscalar microprocessors. It is not practical, given the environment of a pipelined microprocessor, to sequentially search each and every entry in a deallocation vector in order to discover, at the same instant, several vacant entries within the instruction scheduler. Since it is desired for pipelined microprocessors to execute portions of several instructions in parallel, it is unacceptable for there to be any delays associated with the search procedure of the deallocation vector of the instruction scheduler. This procedure must operate within a single clock cycle. Delays associated with such a task would reduce overall microprocessor efficiency and speed. Further, such processing delays may tend to eliminate the expansive advantages offered by microprocessors adopting pipeline architecture and associated microprocessor technology.
Therefore, what is desired is a processing scheme and apparatus that would allow very rapid searching of a deallocation vector in order to find, in one clock cycle, several vacant entries within an instruction scheduler. Further, what is needed is a processing scheme that allows interrogation of a deallocation vector taking into account, for a current clock cycle, the effects of allocations performed in previous pipestages that may not yet have become realized within the reservation station or its deallocation vector during the current cycle. The present invention offers such advantageous capability.
Accordingly, it is an object of the present invention to provide a method and apparatus for searching a deallocation vector, within a single clock cycle, in order to locate several vacancies within a reservation station of an instruction scheduler. It is further an object of the present invention to provide the interrogation of the deallocation vector and to provide free entries for allocation within a two cycle pipeline. It is an object of the present invention within this two cycle pipeline to account, within a current clock cycle, for the effects of allocations performed in previous pipestages that may not yet have become realized within the reservation station or its deallocation vector during the current cycle. Other objects of the present invention not specifically mentioned herein will become clear within the discussions herein.